package cn.lishiyuan.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * 示例 2：
 *
 * 输入：nums = [0,1]
 * 输出：[[0,1],[1,0]]
 * 示例 3：
 *
 * 输入：nums = [1]
 * 输出：[[1]]
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 6
 * -10 <= nums[i] <= 10
 * nums 中的所有整数 互不相同
 */
public class LeetCode46 {


    public static <T> List<List<T>> resolve(T[] nums) {
        List<List<T>> permutations = permutations(nums, 0);
        return permutations;
    }

    /**
     * 递归解决全排列
     * @param nums
     * @param start
     * @return
     * @param <T>
     */
    private static <T> List<List<T>> permutations(T[]nums,int start){

        List<List<T>> res = new ArrayList<>();

        if(start == nums.length - 1){
            res.add(Collections.singletonList(nums[start]));
            return res;
        }

        for(int i = start;i < nums.length;i++){
            // 当前元素为首位的全排列结果
            List<List<T>> list = new ArrayList<>();
            // 将i 与 start交换位置，剩下的start - 1进行全排列
            T temp = nums[i];
            nums[i] = nums[start];
            nums[start] = temp;
            List<List<T>> permutations = permutations(nums, start + 1);
            for (List<T> permutation : permutations) {
                // 组合全排列结果
                List<T> c = new ArrayList<>();
                c.add(nums[start]);
                c.addAll(permutation);
                list.add(c);
            }
            res.addAll(list);
            // 交换回去
            nums[start] = nums[i];
            nums[i] = temp;

        }
        return res;
    }

}
